package pers.qianyu.month_202012.date_20201219.sort;

import org.junit.*;

import java.util.*;

/**
 * 快速排序练习
 *
 * @author mizzle rain
 * @date 2020年12月19日13:49:34
 */
public class QuickSortTest {
    private void quickSort(int[] arr) {
        quickSort(arr, 0, arr.length - 1);
    }

    private void quickSort(int[] arr, int left, int right) {
        if (left < right) {
            int pivot = partition(arr, left, right);
            quickSort(arr, left, pivot - 1);
            quickSort(arr, pivot + 1, right);
        }
    }

    // 根据枢纽排序
    private int partition(int[] arr, int left, int right) {
        selectMid(arr, left, right);
        int pivot = arr[left];
        while (left < right) {
            while (left < right && arr[right] >= pivot) {
                right--;
            }
            arr[left] = arr[right];
            while (left < right && arr[left] <= pivot) {
                left++;
            }
            arr[right] = arr[left];
        }
        arr[left] = pivot;
        return left;
    }

    // 三数取中法找到中间数
    private void selectMid(int[] arr, int left, int right) {
        int mid = left + ((right - left) >> 1);
        if (arr[left] > arr[right]) {
            swap(arr, left, right);
        }
        if (arr[mid] > arr[right]) {
            swap(arr, mid, right);
        }
        if (arr[left] < arr[mid]) {
            swap(arr, left, mid);
        }
    }

    // 交换元素
    private void swap(int[] arr, int i, int j) {
        arr[i] = arr[i] ^ arr[j];
        arr[j] = arr[i] ^ arr[j];
        arr[i] = arr[i] ^ arr[j];
    }


    private QuickSortTest s;

    @Before
    public void before() {
        s = new QuickSortTest();
    }

    @Test
    public void testSwap() {
        int[] arr = {1, 2, 3, 4};
        s.swap(arr, 0, 1);
        System.out.println(Arrays.toString(arr));
    }

    @Test
    public void testSelectMid() {
        int[] arr = {1, 2, 3, 4, 5};
        s.selectMid(arr, 0, 4);
        System.out.println(Arrays.toString(arr));
    }

    @Test
    public void testQuickSort() {
        for (int item = 0; item < 20; item++) {
            int[] arr = new int[10];
            for (int i = 0; i < arr.length; i++) {
                arr[i] = (int) (Math.random() * 100);
            }
            System.out.println(Arrays.toString(arr));
            int[] newArr = Arrays.copyOf(arr, arr.length);
            s.quickSort(arr);
            Arrays.sort(newArr);
            System.out.println(Arrays.toString(arr) + "\n");
            Assert.assertArrayEquals(arr, newArr);
        }
    }
}